#include "linkedlist.h"

//initization
void LinkedInitList(List *list)
{
    //创建头结点（此时头结点也是尾结点)
    list->first = list->last = NODE;
    assert(list->first != NULL);
    //为结点赋值
    list->first->next = NULL;
    list->size = 0;
}

//insert data at the end,create the empty node to linkedlist
void linked_push_back(List *list, ElemType x)
{
    //创建尾插结点
    Node *s = NODE;
    assert(s != NULL);
    //赋值
    s->data = x;
    s->next = NULL;
    //将尾插结点连接到链表尾部
    list->last->next = s;
    list->last = s;
    //更改有效结点个数
    list->size++;
}

//insert data at the front
void linked_push_front(List *list, ElemType x)
{
    Node *s = NODE;
    assert(s != NULL);
    s->data = x;
    //将头结点连接到链表中
    s->next = list->first->next;
    list->first->next = s;
    ////如果这个是插入的第一个有效结点，需要更改尾指针的指向
    if (list->size == 0)
    {
        list->last = s;
    }
    list->size++;
}

//show data
void linked_show_list(List *list)
{
    Node *p = list->first->next;
    while (p != NULL)
    {
        printf("%d-->", p->data);
        p = p->next;
    }
    printf("Nul. \n");
}

//deleted in the end;
void linked_pop_back(List *list)
{
    if (list->size == 0)
    {
        return;
    }
    //寻找倒数第二个结点
    Node *p = list->first;
    while (p->next != list->last)
    {
        p = p->next;
    }
    free(list->last);
    list->last = p;
    list->last->next = NULL;
    list->size--;
}

//delete in the front
void linked_pop_front(List *list)
{
    if (list->size == 0)
    {
        return;
    }
    //临时保存要删除的结点
    Node *p = list->first->next;
    //删除该结点与链表的链接
    list->first->next = p->next;
    //删除结点
    free(p);
    if (list->size == 1)
    {
        list->last = list->first;
    }
    list->size--;
}

//按值插入(按照链表内的数据从小到大排序的规则进行插入)
void linked_insert_val(List *list, ElemType x)
{
    //创建要插入链表的结点
    Node *s = NODE;
    assert(s != NULL);
    s->data = x;
    s->next = NULL;

    //查找要插入的位置
    Node *p = list->first;
    while (p->next != NULL && p->next->data < x)
    {
        p = p->next;
    }
    //判断位置是否为尾部
    if (p->next == NULL)
    {
        list->last = s;
    }
    //将结点插入
    s->next = p->next;
    p->next = s;
    list->size++;
}

//查找某数据在链表中第一次出现的数据结点
Node *linked_find(List *list, ElemType x)
{
    Node *p = list->first->next;
    while (p != NULL && p->data != x)
    {
        p = p->next;
    }
    return p;
}

//查找有效结点的个数
int linked_length(List *list)
{
    return list->size;
}

//删除链表中某值第一次出现的结点
//按照值来删除方法一：查找要删除结点位置来进行删除
void linked_delete_val(List *list, ElemType x)
{
    //判断链接是否为空
    if (list->size == 0)
        return;
    //查找要删除结点的位置
    Node *p = linked_find(list, x);
    //如果没有找到
    if (p == NULL)
    {
        printf("not found data.\n");
        return;
    }
    //如果找到，且这个结点是尾结点
    if (p == list->last)
    {
        //对这个结点进行尾删
        linked_pop_back(list);
    } else
    {//删除方法：拷贝下一结点到当前结点，删除下一结点
        //保存
        Node *q = p->next;
        p->data = q->data;
        p->next = q->next;
        free(q);
        list->size--;
    }

}

//按照值来删除方法二：查找要删除结点的前驱结点位置来进行删除
void linked_delete_val2(List *list, ElemType x)
{
    if (list->size == 0)
        return;
    Node *p = list->first;
    while (p->next != NULL && p->next->data != x)
    {
        p = p->next;
    }
    if (p->next == NULL)
    {
        printf("Not found data. \n");
        return;
    }
    if (p->next == list->last)
    {
        linked_pop_back(list);
    } else
    {
        Node *q = p->next;
        p->next = q->next;
        free(q);
        list->size--;
    }
}

//排序(从小到大)
/**
 * 结点的位置不动，对结点中的数据进行交换排序。
 * 思路二：将一个链表断开分成两个链表（第一个链表包含头结点和第一个有效结点，第二链表包含剩余的有效结点），
 * 从第二个链表中逐一取出数据并按照从小到大的规则逐一插入到第一个链表中。
 * @param list
 */
void linked_order(List *list)
{
    if (list->size == 0 || list->size == 1)
        return;
    //将链表分成两个链表
    Node *s = list->first->next; //保存第一个链表的指针
    Node *q = s->next; //保存第二个链表的指针
    //断开两个链表的连接
    list->last = s;
    list->last->next = NULL;
    //判断第二个链接是否还有结点
    while (q != NULL)
    {
        //从第二个链表不断的取出结点 ，放到 第一个链表S
        s = q;
        q = q->next; //取出一个结点后q后移一位
        //在第一个链表中查找要插入结点的前驱结点
        Node *p = list->first;
        while (p->next != NULL && p->next->data < s->data)
        {
            p = p->next;
        }
        if (p->next == NULL)
        {
            list->last = s;
        }
        s->next = p->next;
        p->next = s;

    }
}

//逆序
void linked_resver(List *list)
{
    if (list->size == 0 || list->size == 1)
    {
        return;
    }
    Node *p = list->first->next;
    Node *q = p->next;
    //断开连接
    list->last = p;
    list->last->next = NULL;

    while (q != NULL)
    {
        p = q;
        q = p->next;
        //头插到第一个链表
        p->next = list->first->next;
        list->first->next = p;
    }
}

//清除链表 不断进行头删，当有效结点都删除完成之后，将尾指针指向头结点，将有效结点个数设置为0
void linked_clear(List *list)
{
    if (list->size == 0)
    {
        return;
    }
    Node *p = list->first->next;
    while (p != NULL)
    {
        list->first->next = p->next;
        free(p);
        p = list->first->next;
    }
    list->last = list->first;
    list->size = 0;
}

//销毁链表 释放所有结点即包括头结点和有效结点
void linked_destory(List *list)
{
    linked_clear(list);
    free(list->first);
    list->first = list->last = NULL;
}

//Node* _buynode(ElemType x){
//    //为结点分配空间
//    Node *s = (Node *)malloc(sizeof(Node));
//    assert(s != NULL);
//    //为该结点的数据域赋值
//    s->data = x;
//    //对应指针域，当结点插入链表时再对其进行赋值，目前先置空
//    s->next = NULL;
//    return s;
//}

it begin(List *list)
{
    return list->first->next;
}

it end(List *list)
{
    return list->last->next;
}

void linked_insert(List *list, it pos, ElemType x)
{
    //找到结点要插入的位置
    Node *p = list->first;
    while (p->next != pos)
    {
        p = p->next;
    }
    //获取一个结点
    Node *s = _buynode(x);
    //将该结点插入链表
    s->next = p->next;
    p->next = s;
    //如果插入结点的位置在尾部，需要更改尾指针的值
    if (pos == NULL)
        list->last = s;
    //更改有效结点个数
    list->size++;
}